package com.leetcode.solution.s7x;

import java.util.HashMap;
import java.util.Map;

public class Minwindow76 {
    public static void main(String[] args) {
        String minWin = new Minwindow76().minWindow("ADOBECODEBANC", "ABC");

        System.out.println("final minWin:" + minWin);
    }

    public String minWindow(String s, String t) {
        // make t Map
        Map<Character, Integer> targetMap = new HashMap<>();
        int num;
        for (char chT : t.toCharArray()) {
            targetMap.put(chT, targetMap.getOrDefault(chT, 0) + 1);
        }

        int matchNum = 0;
        int left = 0;
        int right = 0;
        int start = 0;
        int len = Integer.MAX_VALUE;
        Map<Character, Integer> checkMap = new HashMap<>();
        char ch;
        while (right < s.length()) {
            ch = s.charAt(right);
            right++;

            if (targetMap.containsKey(ch)) {
                checkMap.put(ch, checkMap.getOrDefault(ch, 0) +  1);
                if (checkMap.get(ch).equals(targetMap.get(ch))) {
                    matchNum++;
                }
            }

            while (matchNum == targetMap.size()) {
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }

                ch = s.charAt(left);
                left++;
                if (targetMap.containsKey(ch)) {
                    if (checkMap.get(ch).equals(targetMap.get(ch))) {
                        matchNum--;
                    }

                    checkMap.put(ch, checkMap.getOrDefault(ch, 0) - 1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
    }
}
